package cn.aylog.search;

/**
 * 斐波那契(黄金分割点)查找
 */
public class FibSearch {
    public static void main(String[] args) {
        int len = 20;
        int[] cache = new int[len + 1];
        // 1 1 2 3 5 8 13 21 34 55
        System.out.println(fib(len, cache));
    }

    public static int fib(int n, int[] cache) {
        if(cache[n] != 0) return cache[n];
        if (n == 0) return 0;
        if (n <= 2) return 1;
        int sum = fib(n - 1, cache) + fib(n - 2, cache);
        cache[n] = sum;
        return sum;
    }
}
